package com.jacklei.ch09;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/*
* 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

 

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 

提示:

1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
//遇到字符串中有重复的字符  ,hashMap  不能解此题
public class FindAllAnagramsInAString {
    public static void main(String[] args) {
        FindAllAnagramsInAString f = new FindAllAnagramsInAString();
        List<Integer> anagrams = f.findAnagrams("abab", "ab");
        for (Integer anagram : anagrams) {
            System.out.println(anagram);
//            "abab"
//            "ab"
        }
    }
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        HashMap<Character , Integer> map = new HashMap<>();
        HashSet<Integer> set = new HashSet<>();
        int lS = s.length();
        int lP = p.length();
        int i = lP-1;
        for (int k = 0; k < lP; k++) {
            map.put(p.charAt(k),k);
        }
        char beforeChar = 0;
        boolean isBefore = false;
        while (i < lS){
            if(isBefore){
                if(beforeChar ==  s.charAt(i)){
                    res.add(i-(lP-1));
                    i++;
                    beforeChar = s.charAt(i-lP);
                    continue;
                }else {
                    isBefore = false;
                    i += (lP-1);
                    continue;
                }
            }
            if (map.containsKey(s.charAt(i))){
                int j = i;
                i -= (lP-1);
                while (i < lS && map.containsKey(s.charAt(i))){
                    if(set.contains(map.get(s.charAt(i)))) break;
                    set.add(map.get(s.charAt(i++)));
                    if(set.size() == lP)  break;
                }
                if(set.size() == lP){
                    set.clear();
                    res.add(j - (lP-1));
                    isBefore = true;
                    beforeChar = s.charAt(j - (lP-1));
                    i = j+1;
                }else {
                    set.clear();
                    i = j + 1;
                }
            }else {
                set.clear();
                i += (lP-1);
            }

        }
        return  res;
    }
}
